#include "../../lib/common.h"
#define N 10

int binary_search_insertion(const int *arr, const int size, int target);
int binary_search_insertion2(const int *arr, const int size, int target);

int main(void)
{
  int index;

  /* 原数组中无重复元素 */
  int arr[N] = {1, 3, 6, 8, 12, 15, 23, 26, 31, 35};
  index = binary_search_insertion(arr, N, 6);
  printf("%d\n", index);
  index = binary_search_insertion(arr, N, 7);
  printf("%d\n", index);
  puts("\n");

  /* 原数组中有重复元素 */
  int arr2[N] = {1, 3, 6, 6, 6, 6, 6, 8, 12, 15};
  index = binary_search_insertion2(arr2, N, 6);
  printf("%d\n", index);
  index = binary_search_insertion2(arr2, N, 7);
  printf("%d\n", index);

  return 0;
}

/**
 * 原数组中无重复元素（target可能和数组中某个元素相等）
 */
int binary_search_insertion(const int *arr, const int size, int target)
{
  int i = 0, j = size - 1;
  int m;
  while (i <= j) // 二分查找寻找和target相等的元素
  {
    m = i + (j - i) / 2;
    if (arr[m] < target)
      i = m + 1;
    else if (arr[m] == target)
      return m;
    else
      j = m - 1;
  }
  return i; // 数组中不存在和target相等的元素，收缩区间之后i就是插入点
}

/**
 * 原数组中有重复元素，继续使用二分法将区间缩小为一个点
 */
int binary_search_insertion2(const int *arr, const int size, int target)
{
  int i = 0, j = size - 1; // 初始化双闭区间 [0, n-1]
  int m;
  while (i <= j)
  {
    m = i + (j - i) / 2; // 计算中点索引 m
    if (arr[m] < target) i = m + 1; // target 在区间 [m+1, j] 中
    else if (arr[m] > target) j = m - 1; // target 在区间 [i, m-1] 中
    else j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
  }
  // 返回插入点 i
  return i;
}
